package basic.sort.string;

import javax.print.attribute.PrintServiceAttributeSet;

/**
 * @author distantstar
 * @version 1.0
 * @date 2021
 * @description basic.sort.string
 * @since JDK1.8
 *
 * 规定，长串叫做s，短串叫做t
 *
 * 常规的子串查找的流程就是：
 *      比对s0位置和t0位置是否相等：
 *          如果相等，则对比下一个；
 *          不等，则s比对的位置回到1位置，而t比对的位置回到0位置
 *      按照此过程，一次比对每一位。
 * 可以发现这种方法的最差时间复杂度就是
 * 每一次比较，刚好是最后一个字符不同，然后又从头重新开始
 * 则时间复杂度为O(N * M)(N为s长度，M为t长度)
 *
 * 而KMP对此的改进有两个：
 *      1：计算出t中每一个字符其前面的字符串的前缀和后缀相等的最长长度，放到一个next数组里面去
 *         规定，0位置为-1，1位置为0
 *      2：比对字符时，假如比对到某一个字符不相等时，这是并不回调s的字符位置，而是回调t的字符位置，
 *         回调的位置为next[j](j为此时位置)，然后再进行比对。
 *         假如比对到最后，next[j] == -1，则s的字符位置向后移动。
 *
 */
public class KMP {

    /**
     * 找到t在s中的位置
     * @param s 长串
     * @param t 短串
     * @return t是s的子串，就返回查找到的索引位置；否则返回-1
     */
    private static int getIndex(String s, String t) {
        if (s == null || t == null || s.length() < 1 || s.length() < t.length()) {
            return -1;
        }

        // 将字符串转换成字符数组
        char[] charS = s.toCharArray();
        char[] charT = t.toCharArray();

        // 字符数组的索引
        int cs = 0;
        int ct = 0;

        // 计算t中每一个字符的前缀和后缀相等的最长长度
        int[] next = getNext(charT);

        // 循环比对
        while (cs < charS.length && ct < charT.length) {
            // 如果比对的字符相等，则俩索引都++
            if (charS[cs] == charT[ct]) {
                cs++;
                ct++;
            } else if(next[ct] != -1) {
                // 如果比对的字符不等，且next[ct] ！= -1，则ct = next[ct]
                ct = next[ct];
            } else {
                // 否则，移动cs的位置
                cs++;
            }
        }

        // 最后判断是ct是否越界
        return ct == charT.length ? cs - ct : -1;
    }

    /**
     * 获取每一位字符的相等缀的最长长度
     * @param charT 目标字符数组
     * @return 返回计算好的数组
     */
    private static int[] getNext(char[] charT) {
        if (charT.length == 1) {
            return new int[]{-1};
        }

        // 新建数组
        int[] next = new int[charT.length];

        // 初始化数组
        next[0] = -1;
        next[1] = 0;

        // 当前和i-1位置比较的字符的位置
        int tempRecord = 0;
        // 当前查找的字符位置
        int i = 2;

        // 循环查找
        while (i < charT.length) {
            // 假如当前位置的后缀和前缀的最后一个字符相等，则记录值
            if (charT[i - 1] == charT[tempRecord]) {
                next[i++] = ++tempRecord;
            } else if (tempRecord > 0) {
                // 如果不等，并且前缀位置不为0，则查找改位置的前缀的后一位
                tempRecord = next[tempRecord];
            } else {
                // 否则，将此位置的长度变为0
                next[i++] = 0;
            }
        }

        return next;
    }

    private static String getRandomString(int possibilities, int size) {
        char[] ans = new char[(int) (Math.random() * size) + 1];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = (char) ((int) (Math.random() * possibilities) + 'a');
        }
        return String.valueOf(ans);
    }

    public static void main(String[] args) {
        int possibilities = 5;
        int strSize = 20;
        int matchSize = 5;
        int testTimes = 5000000;
        System.out.println("test begin");
        for (int i = 0; i < testTimes; i++) {
            String str = getRandomString(possibilities, strSize);
            String match = getRandomString(possibilities, matchSize);
            if (getIndex(str, match) != str.indexOf(match)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("test finish");
    }
}
